{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Insertions to Balance a Parentheses String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minInsertions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #平衡括号字符串的最少插入次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个括号字符串&nbsp;<code>s</code>&nbsp;，它只包含字符&nbsp;<code>&#39;(&#39;</code> 和&nbsp;<code>&#39;)&#39;</code>&nbsp;。一个括号字符串被称为平衡的当它满足：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>任何左括号&nbsp;<code>&#39;(&#39;</code>&nbsp;必须对应两个连续的右括号&nbsp;<code>&#39;))&#39;</code>&nbsp;。</li>\n",
    "\t<li>左括号&nbsp;<code>&#39;(&#39;</code>&nbsp;必须在对应的连续两个右括号&nbsp;<code>&#39;))&#39;</code>&nbsp;之前。</li>\n",
    "</ul>\n",
    "\n",
    "<p>比方说&nbsp;<code>&quot;())&quot;</code>，&nbsp;<code>&quot;())(())))&quot;</code> 和&nbsp;<code>&quot;(())())))&quot;</code>&nbsp;都是平衡的，&nbsp;<code>&quot;)()&quot;</code>，&nbsp;<code>&quot;()))&quot;</code> 和&nbsp;<code>&quot;(()))&quot;</code>&nbsp;都是不平衡的。</p>\n",
    "\n",
    "<p>你可以在任意位置插入字符 &#39;(&#39; 和 &#39;)&#39; 使字符串平衡。</p>\n",
    "\n",
    "<p>请你返回让 <code>s</code>&nbsp;平衡的最少插入次数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;(()))&quot;\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>第二个左括号有与之匹配的两个右括号，但是第一个左括号只有一个右括号。我们需要在字符串结尾额外增加一个 &#39;)&#39; 使字符串变成平衡字符串 &quot;(())))&quot; 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;())&quot;\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>字符串已经平衡了。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;))())(&quot;\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>添加 &#39;(&#39; 去匹配最开头的 &#39;))&#39; ，然后添加 &#39;))&#39; 去匹配最后一个 &#39;(&#39; 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;((((((&quot;\n",
    "<strong>输出：</strong>12\n",
    "<strong>解释：</strong>添加 12 个 &#39;)&#39; 得到平衡字符串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;)))))))&quot;\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>在字符串开头添加 4 个 &#39;(&#39; 并在结尾添加 1 个 &#39;)&#39; ，字符串变成平衡字符串 &quot;(((())))))))&quot; 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10^5</code></li>\n",
    "\t<li><code>s</code>&nbsp;只包含&nbsp;<code>&#39;(&#39;</code> 和&nbsp;<code>&#39;)&#39;</code>&nbsp;。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-insertions-to-balance-a-parentheses-string](https://leetcode.cn/problems/minimum-insertions-to-balance-a-parentheses-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-insertions-to-balance-a-parentheses-string](https://leetcode.cn/problems/minimum-insertions-to-balance-a-parentheses-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"(()))\"', '\"())\"', '\"))())(\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        arr1 = [0] * n\n",
    "        i = n - 1\n",
    "        while i >= 0:\n",
    "            arr2 = [0] * n\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    arr2[j] = arr1[j - 1]\n",
    "                    continue\n",
    "                arr2[j] = min(arr1[j], arr2[j - 1]) + 1\n",
    "            arr1 = arr2\n",
    "            i -= 1\n",
    "        return arr1[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minInsertions(self, s: str) -> int:\n",
    "#         n = len(s)\n",
    "#         t = s[::-1]\n",
    "#         寻找最长公共子序列，也是为了寻找序列的最长回文子序列，之后对于不在回文子序列中的字符，依据在回文中心的左右两侧，在对侧填补相同字符\n",
    "#         dp = [[0] * (n+1) for _ in range(n+1)]\n",
    "#         for i in range(1,n+1):\n",
    "#             for j in range(1,n+1):\n",
    "#                 dp[i][j] = max(dp[i-1][j],dp[i][j-1])\n",
    "#                 if s[i-1] == t[j-1]:\n",
    "#                     dp[i][j] = max(dp[i][j],dp[i-1][j-1]+1)\n",
    "#         return n - dp[n][n]\n",
    "\n",
    "# 动态区间规划\n",
    "# dp[i][j] 表示对于字符串 s 的子串 s[i:j] 最少添加的字符数量使满足要求\n",
    "class Solution:\n",
    "    def minInsertions(self,s:str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for span in range(2,n + 1):\n",
    "            for i in range(n- span + 1):\n",
    "                j = i + span -1\n",
    "                dp[i][j] = min(dp[i+1][j],dp[i][j-1]) + 1\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = min(dp[i][j],dp[i+1][j-1])\n",
    "        return dp[0][n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        ans = int(1e9)\n",
    "\n",
    "        dp = [[0]*(len(s)+1) for _ in range(len(s)+1)]\n",
    "        for sep in range(len(s)+1):\n",
    "            lf = s[:sep]\n",
    "            rt = s[sep:]\n",
    "            rt = rt[::-1]\n",
    "            m, n = len(lf), len(rt)\n",
    "            dif = abs(m - n)\n",
    "            min_len = min(m, n)\n",
    "            \n",
    "\n",
    "            def val(x, y):\n",
    "                return 0 if x<0 or y<0 else dp[x][y]\n",
    "            \n",
    "            for j in range(len(rt)):\n",
    "                if lf != '' and rt != '':\n",
    "                    if lf[sep-1] == rt[j]:\n",
    "                        dp[sep][j] = val(sep-1,j-1)+1\n",
    "                    else:\n",
    "                        dp[sep][j] = max(val(sep-1, j), val(sep, j-1))\n",
    "            ans = min(ans, dif + (min_len-dp[sep][len(rt)-1])*2) \n",
    "\n",
    "        dp = [[0]*(len(s)+1) for _ in range(len(s)+1)]\n",
    "        for sep in range(len(s)):\n",
    "            lf = s[:sep]\n",
    "            rt = s[sep+1:]\n",
    "            rt = rt[::-1]\n",
    "            m, n = len(lf), len(rt)\n",
    "            dif = abs(m - n)\n",
    "            min_len = min(m, n)\n",
    "            \n",
    "\n",
    "            def val(x, y):\n",
    "                return 0 if x<0 or y<0 else dp[x][y]\n",
    "            \n",
    "            for j in range(len(rt)):\n",
    "                if lf != '' and rt != '':\n",
    "                    if lf[sep-1] == rt[j]:\n",
    "                        dp[sep][j] = val(sep-1,j-1)+1\n",
    "                    else:\n",
    "                        dp[sep][j] = max(val(sep-1, j), val(sep, j-1))\n",
    "            ans = min(ans, dif + (min_len-dp[sep][len(rt)-1])*2)  \n",
    "    \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        s1 = s[::-1]\n",
    "        length = len(s)\n",
    "        dp = [[0] * (length+1) for _ in range(length+1)]\n",
    "        for k in range(length+1):\n",
    "            dp[k][0] = k\n",
    "            dp[0][k] = k\n",
    "        for i in range(1, length+1):\n",
    "            for j in range(1, length+1):\n",
    "                if s[i-1] != s1[j-1]:\n",
    "                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j-1] \n",
    "        return dp[-1][-1] // 2\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        dp = [[float('inf') for _ in range(len(s))] for _ in range(len(s))]\n",
    "        for i in range(len(s)):\n",
    "            dp[i][i] = 0\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    if i == j + 1:\n",
    "                        dp[i][j] = 0\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i - 1][j + 1]\n",
    "                else:\n",
    "                    if i == j + 1:\n",
    "                        dp[i][j] = 1\n",
    "                    else:\n",
    "                        dp[i][j] = min(dp[i][j + 1], dp[i - 1][j]) + 1\n",
    "        return dp[-1][0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        memo = [[-1] * len(s) for _ in range(len(s))]\n",
    "        def dp(a, b):\n",
    "            if a >= b:\n",
    "                return 0\n",
    "            if memo[a][b] > -1:\n",
    "                return memo[a][b]\n",
    "            if s[a] == s[b]:\n",
    "                res = dp(a+1, b-1)\n",
    "            else:\n",
    "                res = min(dp(a, b-1), dp(a + 1, b)) + 1\n",
    "            memo[a][b] = res\n",
    "            return res\n",
    "        return dp(0, len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        self.memo = [[-1 for _ in range(len(s))] for _ in range(len(s))]\n",
    "        def dp(i ,j):\n",
    "            if i >= j: return 0\n",
    "            if self.memo[i][j] != -1: return self.memo[i][j]\n",
    "            if s[i] == s[j]: self.memo[i][j] = dp(i+1, j-1)\n",
    "            else:\n",
    "                self.memo[i][j] = min(dp(i+1, j), dp(i, j-1))+1\n",
    "            return self.memo[i][j]\n",
    "        return dp(0, len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp_table = [[-1]*n for _ in range(n)]\n",
    "\n",
    "        def dp(s, l, r):\n",
    "            if dp_table[l][r] != -1:\n",
    "                return dp_table[l][r]\n",
    "            if l >= r:\n",
    "                return 0\n",
    "            if s[l] == s[r]:\n",
    "                res = dp(s, l+1, r-1)\n",
    "            else:\n",
    "                res = 1+min(\n",
    "                    dp(s, l+1, r),\n",
    "                    dp(s, l, r-1),\n",
    "                )\n",
    "            dp_table[l][r] = res\n",
    "            return res\n",
    "        return dp(s, 0, len(s)-1)\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minInsertions(self, s: str) -> int:\r\n",
    "        def dp(i, j, s):\r\n",
    "            if i > j:\r\n",
    "                return 0\r\n",
    "            \r\n",
    "            if memo[i][j] != -1:\r\n",
    "                return memo[i][j]\r\n",
    "            \r\n",
    "            if s[i] == s[j]:\r\n",
    "                memo[i][j] = dp(i + 1, j - 1, s)\r\n",
    "            else:\r\n",
    "                memo[i][j] = min(dp(i + 1, j, s) + 1, dp(i, j - 1, s) + 1)\r\n",
    "            \r\n",
    "            return memo[i][j]\r\n",
    "                \r\n",
    "\r\n",
    "        \r\n",
    "        memo = [[-1 for _ in range(len(s))] for _ in range(len(s))]\r\n",
    "\r\n",
    "        return dp(0, len(s) - 1, s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        self.s = s\n",
    "        self.rec = {}\n",
    "        x = self.dfs(0, len(s) - 1)\n",
    "        return x\n",
    "\n",
    "\n",
    "    def dfs(self, i, j):\n",
    "        if i >= j:\n",
    "            return 0\n",
    "        if (i, j) in self.rec:\n",
    "            return self.rec[(i, j)]\n",
    "        if self.s[i] == self.s[j]:\n",
    "            self.rec[(i, j)] = self.dfs(i + 1, j - 1)\n",
    "        else:\n",
    "            self.rec[(i, j)] = min(self.dfs(i + 1, j) + 1, self.dfs(i, j -1) + 1)\n",
    "        return self.rec[(i, j)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        self.memo = {}\n",
    "        for i in range(len(s)):\n",
    "            ans = max(self.dp(s, i, i), ans)\n",
    "\n",
    "        return len(s) - ans\n",
    "\n",
    "    def dp(self, s, i, j):\n",
    "        if i < 0 or j >= len(s):\n",
    "            return 0\n",
    "\n",
    "        if (i, j) in self.memo:\n",
    "            return self.memo[(i, j)]\n",
    "\n",
    "        if i == j:\n",
    "            self.memo[(i, j)] = max(1 + self.dp(s, i - 1, j + 1), self.dp(s, i, j + 1), self.dp(s, i - 1, j))\n",
    "        elif s[i] == s[j]:\n",
    "            self.memo[(i, j)] = max(2 + self.dp(s, i - 1, j + 1), self.dp(s, i, j + 1), self.dp(s, i - 1, j)) \n",
    "        else:\n",
    "            self.memo[(i, j)] = max(self.dp(s, i - 1, j + 1), self.dp(s, i, j + 1), self.dp(s, i - 1, j))\n",
    "\n",
    "        return self.memo[(i, j)] \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ok(self,s,t):\n",
    "        n = len(s)\n",
    "        m = len(t)\n",
    "        dp=[[[0,0,0,0] for j in range(m+1)]for i in range(n+1)]\n",
    "        ma = 0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,m+1):\n",
    "                dp[i][j][0]=max(dp[i][j-1][2],dp[i-1][j][1],dp[i-1][j-1][3],dp[i][j-1][0],dp[i-1][j][0])\n",
    "                if(s[i-1]==t[j-1]):\n",
    "                    dp[i][j][3]=max(dp[i-1][j][1]+1,dp[i][j-1][2]+1,dp[i-1][j][0]+1,dp[i][j-1][0]+1)\n",
    "                    try:\n",
    "                        dp[i][j+1][1]=dp[i][j][3]\n",
    "                    except:pass\n",
    "                    try:\n",
    "                        dp[i+1][j][2]=dp[i][j][3]\n",
    "                    except:pass\n",
    "                else:\n",
    "                    dp[i][j][1] = max(dp[i][j-1][1],dp[i][j][1])\n",
    "                    dp[i][j][2] = max(dp[i-1][j][2],dp[i][j][2])\n",
    "        ma=max(dp[n][m])\n",
    "        #for i in dp:print(i)\n",
    "        return ma\n",
    "        kk=0\n",
    "        j=0\n",
    "        for i in range(len(t)):\n",
    "            if(s[j]==t[i]):\n",
    "                kk+=1\n",
    "        return kk\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        kk=0;nooo=0\n",
    "        nn=self.ok(s,s[-1::-1])\n",
    "        return n-nn\n",
    "        for i in range(n-1):\n",
    "            s1=s[i::-1];s2=s[i+2:]\n",
    "            s3=s[i+1:]\n",
    "            kk3=self.ok(s1,s3)\n",
    "            kk1=self.ok(s1,s2)\n",
    "            #print(kk1,kk3,s1,s2,s3)\n",
    "            if(kk3>kk and kk3>kk1):\n",
    "                #print(kk3)\n",
    "                nooo=1\n",
    "            if(kk1>=kk and kk1>=kk3):\n",
    "                #print(kk1,\"?\")\n",
    "                nooo=0\n",
    "            kk=max(kk1,kk,kk3)\n",
    "        if(nooo==1):n+=1\n",
    "        return n-kk*2-1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        q = deque()\n",
    "        q.append([0, s])\n",
    "        runed = set()\n",
    "        while q:\n",
    "            step, tmps = q.popleft()\n",
    "            if len(tmps) <= 1:\n",
    "                return step\n",
    "            if tmps[0] == tmps[-1]:\n",
    "                c = tmps[1:-1]\n",
    "                if c in runed:\n",
    "                    continue\n",
    "                runed.add(c)\n",
    "                q.appendleft([step, c])\n",
    "            else:\n",
    "                c = tmps[1:]\n",
    "                if c not in runed:\n",
    "                    runed.add(c)\n",
    "                    q.append([step + 1, c])\n",
    "                c = tmps[:-1]\n",
    "                if c not in runed:\n",
    "                    runed.add(c)\n",
    "                    q.append([step + 1, c])\n",
    "        return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        self.memo = {}\n",
    "        return self.min_insert(s)\n",
    "\n",
    "    def min_insert(self, s):\n",
    "        if s in self.memo:\n",
    "            return self.memo[s]\n",
    "\n",
    "        length = len(s)\n",
    "        half = int(length / 2)\n",
    "        addtion = 1 if length % 2 == 1 else 0\n",
    "\n",
    "        if length <= 1 or s[:half] == s[half + addtion:]:\n",
    "            self.memo[s] = 0\n",
    "            return 0\n",
    "        elif length == 2:\n",
    "            self.memo[s] = 1\n",
    "            return 1\n",
    "\n",
    "        last = length - 1\n",
    "        first = 0\n",
    "        while first < last and s[first] == s[last]:\n",
    "            first += 1\n",
    "            last -= 1\n",
    "\n",
    "        if first >= last:\n",
    "            return 0\n",
    "\n",
    "        self.memo[s] = min(self.min_insert(s[first + 1:last + 1]), self.min_insert(s[first:last])) + 1\n",
    "        return self.memo[s]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    def __init__(self) -> None:\n",
    "        self.dict = {}\n",
    "    @functools.lru_cache\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n == 2:\n",
    "            return 0 if s[0] == s[-1] else 1\n",
    "        if s in self.dict:\n",
    "            return self.dict[s]\n",
    "        if s[0] == s[-1]:\n",
    "            res = self.minInsertions(s[1:n-1])\n",
    "        else:\n",
    "            l = self.minInsertions(s[:n-1])\n",
    "            r = self.minInsertions(s[1:])\n",
    "            res = min(l,r)+1\n",
    "        self.dict[s] = res\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.dp = {}\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        res = s[::-1]\n",
    "        return len(s) - len(self.longestCommonSubsequence(s, res))\n",
    "\n",
    "    def longestCommonSubsequence(self,text1: str, text2: str) -> int:\n",
    "        text1_idx, text2_idx = \\\n",
    "            len(text1) - 1, len(text2) - 1\n",
    "        key = '%s-%s' % (text1_idx, text2_idx)\n",
    "        if key in self.dp.keys():\n",
    "            return self.dp[key]\n",
    "        tmp_sub_seq = ''\n",
    "        while text1_idx >= 0 and text2_idx >= 0:\n",
    "            if text1[text1_idx] == text2[text2_idx]:\n",
    "                tmp_sub_seq = text1[text1_idx] + tmp_sub_seq\n",
    "                text1_idx, text2_idx = \\\n",
    "                    text1_idx - 1, text2_idx - 1\n",
    "            else:\n",
    "                tmp1 = self.longestCommonSubsequence(text1[:text1_idx],\n",
    "                                                text2[:text2_idx+1])\n",
    "                tmp2 = self.longestCommonSubsequence(text1[:text1_idx+1],\n",
    "                                                text2[:text2_idx])\n",
    "                tmp_sub_seq = (tmp1 if len(tmp1) > len(tmp2) else tmp2) + tmp_sub_seq\n",
    "                break\n",
    "        self.dp[key] = tmp_sub_seq\n",
    "        return tmp_sub_seq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minInsertions(self, s: str) -> int:\r\n",
    "        df = {(i,j):0 for i in range(len(s)) for j in range(len(s))}\r\n",
    "        for d in range(1,len(s)):\r\n",
    "            for i in range(len(s) - d):\r\n",
    "                j = i + d\r\n",
    "                if s[i] == s[j]:\r\n",
    "                    df[(i,j)] = df[(i+1,j-1)]\r\n",
    "                else:\r\n",
    "                    df[(i,j)] = min(df[(i+1,j)], df[(i,j-1)]) + 1\r\n",
    "        # print(df)\r\n",
    "        return df[(0,len(s)-1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        dp = [[0 for _ in range(len(s))] for _ in range(len(s))]\n",
    "\n",
    "        memo = {}\n",
    "\n",
    "        def helper(i, j):\n",
    "            if (i, j) in memo:\n",
    "                return dp[i][j]\n",
    "            if i == j:\n",
    "                dp[i][j] = 0\n",
    "                memo[i, j] = True                \n",
    "            if i == j - 1:\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = 0\n",
    "\n",
    "                else:\n",
    "                    dp[i][j] = 1\n",
    "                memo[i, j] = True\n",
    "            if i < j - 1:\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = min(helper(i + 1, j - 1), helper(i, j - 1) + 1, helper(i + 1, j) + 1)\n",
    "                else:\n",
    "                    dp[i][j] = min(helper(i + 1, j - 1) + 2,\n",
    "                                   helper(i, j - 1) + 1, helper(i + 1, j) + 1)\n",
    "                memo[i,j] = True\n",
    "            return dp[i][j]\n",
    "        helper(0, len(s) - 1)\n",
    "        return dp[0][len(s) - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "\n",
    "        # 定义尝试模型\n",
    "        # 返回s[l:r+1]成为回文串的最少操作次数\n",
    "        dp = {}\n",
    "        def p(l, r):\n",
    "            # base case\n",
    "            if l >= r:\n",
    "                return 0\n",
    "            # 记忆化搜索\n",
    "            name = '{},{}'.format(l, r)\n",
    "            if name in dp:\n",
    "                return dp[name]\n",
    "\n",
    "            # 状态转移\n",
    "            # 情况一，如果s[l] == s[r], 那么只需要把中间变成回文串就可以了\n",
    "            if s[l] == s[r]:\n",
    "                res = p(l+1, r-1)\n",
    "            # 情况二，如果s[l] != s[r], 那么就只需要交叉插入2个(bdc->bcdcb),\n",
    "            # 或者使用p将s[l+1:r]变成回文，然后加一个就可以(bcc->bccb)\n",
    "            else:\n",
    "                res = min(p(l+1, r-1) + 2, p(l+1, r) + 1, p(l, r-1) + 1)\n",
    "            dp[name] = res\n",
    "            return res\n",
    "        times = p(0, len(s) - 1)\n",
    "        return times"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        # dp = [[0]*len(s) for _ in s]\n",
    "        # for i in range(len(s)):\n",
    "        #     dp[i][i] = 1\n",
    "        #     for j in range(i-1,-1,-1):\n",
    "        #         if s[i]==s[j]:\n",
    "        #             dp[i][j] = dp[i-1][j+1]+2\n",
    "        #         else:\n",
    "        #             dp[i][j]=max(dp[i][j+1],dp[i-1][j])\n",
    "        # return len(s) - dp[-1][0]\n",
    "        @lru_cache(30000)\n",
    "        def dp(i:int,j:int)->int:\n",
    "            if i > j:\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if s[i] == s[j]:\n",
    "                return dp(i+1,j-1)+2\n",
    "            return max(dp(i+1,j),dp(i,j-1))\n",
    "        return len(s)-dp(0,len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        left, right = 0, len(s) - 1\n",
    "        cache = {}\n",
    "\n",
    "        def count_ops(i, j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "\n",
    "            if (i, j) in cache:\n",
    "                return cache[(i, j)]\n",
    "\n",
    "            if s[i] == s[j]:\n",
    "                cache[(i, j)] = count_ops(i + 1, j - 1)\n",
    "                return cache[(i, j)]\n",
    "            \n",
    "            cache[(i, j)] = 1 + min(count_ops(i, j - 1), count_ops(i + 1, j))\n",
    "            return cache[(i, j)]\n",
    "        \n",
    "        return count_ops(left, right)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            if s[i] == s[j]:\n",
    "                return dfs(i + 1, j - 1)\n",
    "\n",
    "            return 1 + min(dfs(i, j - 1), dfs(i + 1, j))\n",
    "        return dfs(0, len(s) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        @functools.lru_cache(None)\n",
    "        def dp(i, j):\n",
    "            if i>=j:\n",
    "                return 0\n",
    "            if s[i] == s[j]:\n",
    "                return dp(i+1, j-1)\n",
    "            return 1+min(dp(i, j-1), dp(i+1, j))\n",
    "        \n",
    "        return dp(0, n-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "\n",
    "        mem = {}\n",
    "\n",
    "        def dfs(s, l, r):\n",
    "            if (l,r) in mem:\n",
    "                return mem[(l,r)]\n",
    "            rv = 0\n",
    "            if l >= r:\n",
    "                rv = 0\n",
    "            elif s[l] == s[r]:\n",
    "                rv = dfs(s, l+1, r-1)\n",
    "            else:\n",
    "                rv = min(dfs(s, l+1, r-1)+2, dfs(s, l+1, r)+1, dfs(s, l, r-1)+1)\n",
    "\n",
    "            mem[(l,r)] = rv\n",
    "            return rv\n",
    "\n",
    "        return dfs(s, 0, len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        idxes = collections.defaultdict(list)\n",
    "        for i, ch in enumerate(s):\n",
    "            idxes[ch].append(i)\n",
    "            \n",
    "        from functools import lru_cache\n",
    "        @lru_cache(None)\n",
    "        def helper(i, j):\n",
    "            if i >= j: return 0\n",
    "            I = idxes[s[i]]\n",
    "            res = helper(i + 1, j) + 1\n",
    "            ind1 = bisect.bisect_left(I, i)\n",
    "            ind2 = bisect.bisect_right(I, j)\n",
    "            # for idx in I:\n",
    "            #     if idx <= i:continue\n",
    "            #     if idx > j: break\n",
    "            #     res = min(res, helper(i + 1, idx - 1) + j - idx)\n",
    "            # return res\n",
    "            \n",
    "            # for k in range(ind1, ind2):\n",
    "            #     idx = I[k]\n",
    "            #     res = min(res, helper(i + 1, idx - 1) + j - idx)\n",
    "            \n",
    "            if ind2 > ind1:\n",
    "                idx = I[ind2 - 1]\n",
    "                res = min(res, helper(i + 1, idx - 1) + j - idx)\n",
    "            \n",
    "            return res\n",
    "            \n",
    "            \n",
    "            # res1 = helper(i + 1, j - 1) if s[i] == s[j] else j - i + 1\n",
    "            # return min(res1, 1 + helper(i + 1, j))\n",
    "        \n",
    "        \n",
    "        return helper(0, len(s) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i>=j:return 0\n",
    "            if s[i]==s[j]:return dfs(i+1,j-1)\n",
    "            return 1+min(dfs(i,j-1),dfs(i+1,j))\n",
    "        return dfs(0,len(s)-1) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i>=j:\n",
    "                return 0\n",
    "            if s[i] == s[j]:\n",
    "                return dfs(i+1,j-1)\n",
    "            else:\n",
    "                return min(dfs(i,j-1),dfs(i+1,j)) + 1\n",
    "        return dfs(0,len(s)-1)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        \n",
    "        @cache\n",
    "        def dp(i, j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            if s[i] == s[j]:\n",
    "                return dp(i+1, j-1)\n",
    "            else:\n",
    "                return 1 + min(dp(i+1, j), dp(i, j-1))\n",
    "        \n",
    "        return dp(0, len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        @cache\n",
    "        def getcount(left,right):\n",
    "            while left<=right and s[left]==s[right]:\n",
    "                left+=1\n",
    "                right-=1\n",
    "            if right<=left:\n",
    "                return 0\n",
    "            return 1+min(getcount(left+1,right),getcount(left,right-1))\n",
    "        return getcount(0,len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        return self.dp(s,0,len(s)-1)\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def dp(self,s,i,j):\n",
    "        if i==j:\n",
    "            return 0\n",
    "        elif i+1==j:\n",
    "            return 0 if s[i]==s[j] else 1\n",
    "        else:\n",
    "            if s[i]==s[j]:\n",
    "                return self.dp(s,i+1,j-1)\n",
    "            else:\n",
    "                return min(self.dp(s,i+1,j),self.dp(s,i,j-1))+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i>=j: return int(i==j)\n",
    "            \n",
    "            if s[i]==s[j]:\n",
    "                return dfs(i+1,j-1)+2\n",
    "            else:\n",
    "                return min(dfs(i,j-1),dfs(i+1,j))+2\n",
    "        \n",
    "\n",
    "        def make_ans(i,j):\n",
    "            if i>j: return \"\"\n",
    "            if i==j: return s[i]\n",
    "            if s[i]==s[j]:\n",
    "                return s[i]+make_ans(i+1,j-1)+s[j]\n",
    "            if dfs(i,j-1)<=dfs(i+1,j):\n",
    "                return s[j]+make_ans(i,j-1)+s[j]\n",
    "            else:\n",
    "                return s[i]+make_ans(i+1,j)+s[i]\n",
    "        \n",
    "        n=len(s)\n",
    "        return dfs(0,n-1)-n\n",
    "        return len(make_ans(0,n-1))-n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        #记忆化递归\n",
    "        '''\n",
    "        @cache\n",
    "        def dfs(i:int ,j:int):\n",
    "            if i>j:\n",
    "                return 0\n",
    "            if i==j:\n",
    "                return 0\n",
    "            if s[i]==s[j]:\n",
    "                return dfs(i+1,j-1)\n",
    "            return min(dfs(i+1,j)+1,dfs(i,j-1)+1)\n",
    "        return dfs(0,n-1)\n",
    "        '''\n",
    "        #动态规划\n",
    "        # dp=[[0]*(n+1) for _ in range(n+1)]\n",
    "        # for i in range(n-1,-1,-1):\n",
    "        #     for j in range(i+1,n):\n",
    "        #         if s[i]==s[j]:\n",
    "        #             dp[i][j]=dp[i+1][j-1]\n",
    "        #         else:\n",
    "        #             dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1\n",
    "        # return dp[0][n-1]\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i>j:\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return 0\n",
    "            if s[i] == s[j]:\n",
    "                return dfs(i+1,j-1)\n",
    "            return min(dfs(i+1,j)+1,dfs(i,j-1)+1)\n",
    "        return dfs(0,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        need = 0\n",
    "\n",
    "        for i, c in enumerate(s):\n",
    "            if c == '(':\n",
    "                need += 2\n",
    "                if need % 2 == 1:\n",
    "                    ans += 1\n",
    "                    need -= 1\n",
    "            else:\n",
    "                need -= 1\n",
    "                if need == -1:\n",
    "                    ans += 1\n",
    "                    need = 1\n",
    "\n",
    "        return ans + need"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        # 两个连续的右括号才能匹配一个左括号\n",
    "        stack = []\n",
    "        res = 0\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            if s[i] == '(':\n",
    "                stack.append(s[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                if i+1 < len(s) and s[i+1] == ')':\n",
    "                    if stack:\n",
    "                        stack.pop()\n",
    "                    else:\n",
    "                        res += 1\n",
    "                    i += 2\n",
    "                else:\n",
    "                    if stack:\n",
    "                        stack.pop()\n",
    "                        res += 1\n",
    "                    else:\n",
    "                        res += 2\n",
    "                    i += 1\n",
    "        return res + len(stack)*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        res = need = 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                need += 2\n",
    "                if need % 2:\n",
    "                    res += 1\n",
    "                    need -= 1\n",
    "            else:\n",
    "                need -= 1\n",
    "                if need == -1:\n",
    "                    res += 1\n",
    "                    need = 1\n",
    "        return res + need\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        # 配对消除 替换\n",
    "        res = 0\n",
    "        s = s.replace('))', '*')\n",
    "        res += s.count(')')  # 补齐不成对的右括号\n",
    "        s = s.replace(')', '*')\n",
    "        while len(s.replace('(*', '')) != len(s):  # 配对消除\n",
    "            s = s.replace('(*', '')\n",
    "        return res + len(s) + s.count('(')  # 补齐 + 需左括号的右括号对 + 需两个右括号的左括号\n",
    "\n",
    "        # 贪心 维护左括号\n",
    "        length = len(s)\n",
    "        insertions = leftCount = index = 0\n",
    "        while index < length:\n",
    "            if s[index] == \"(\":\n",
    "                leftCount += 1\n",
    "                index += 1\n",
    "            else:\n",
    "                if leftCount > 0:\n",
    "                    leftCount -= 1\n",
    "                else:\n",
    "                    insertions += 1\n",
    "                if index < length - 1 and s[index + 1] == \")\":\n",
    "                    index += 2\n",
    "                else:\n",
    "                    insertions += 1\n",
    "                    index += 1\n",
    "        insertions += leftCount * 2\n",
    "        return insertions\n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        res, need = 0, 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '(':\n",
    "                need += 2\n",
    "                if need % 2 == 1:\n",
    "                    res += 1\n",
    "                    need -= 1\n",
    "            elif s[i] == ')':\n",
    "                need -= 1\n",
    "                if need == -1:\n",
    "                    res += 1\n",
    "                    need = 1\n",
    "        return res + need"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        ans, cnt, stack = 0, 0, 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                if not cnt or (cnt and not stack):\n",
    "                    stack += 1\n",
    "                ans += cnt\n",
    "                cnt = 0\n",
    "            else:\n",
    "                stack -= min(cnt, stack)\n",
    "                if not cnt and not stack:\n",
    "                    ans += 1\n",
    "                cnt = cnt&1^1\n",
    "        return ans + cnt + 2 * (stack - min(cnt, stack))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        # 贪心 维护左括号\n",
    "        length = len(s)\n",
    "        insertions = leftCount = index = 0\n",
    "\n",
    "        while index < length:\n",
    "            if s[index] == \"(\":\n",
    "                leftCount += 1\n",
    "                index += 1\n",
    "            else:\n",
    "                if leftCount > 0:\n",
    "                    leftCount -= 1\n",
    "                else:\n",
    "                    insertions += 1\n",
    "                if index < length - 1 and s[index + 1] == \")\":\n",
    "                    index += 2\n",
    "                else:\n",
    "                    insertions += 1\n",
    "                    index += 1\n",
    "        \n",
    "        insertions += leftCount * 2\n",
    "        return insertions\n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        left_count = 0\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if s[i] == '(':\n",
    "                left_count += 1\n",
    "            else:\n",
    "                if i + 1 < n and s[i + 1] == ')':\n",
    "                    if left_count > 0:\n",
    "                        left_count -= 1 # matched a '('\n",
    "                    else:\n",
    "                        ans += 1 # insert a ')'\n",
    "                    i += 1\n",
    "                    \n",
    "                else: # insert a ')'\n",
    "                    ans += 1\n",
    "                    if left_count == 0:\n",
    "                        ans += 1\n",
    "                    else:\n",
    "                        left_count -= 1\n",
    "            #print('left_count:', left_count)\n",
    "            i += 1\n",
    "            \n",
    "        if left_count > 0:\n",
    "            ans += (left_count * 2)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://labuladong.github.io/algo/di-san-zha-24031/jing-dian--a94a0/ru-he-jie--306f6/\n",
    "# 这道题比较难，res不像前面的题（前面的题，res是维护插入左括号的数量），而这里不是\n",
    "# 这里的reshe need一起维护左右括号的平衡，不区分左右。其实本体一开始是区分左右的，一开始res维护左括号，need维护右括号，但是本题后来就不区分左右了\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        res, need = 0, 0\n",
    "        for c in s:\n",
    "            if c == \"(\":\n",
    "                # 一个左括号对应两个右括号\n",
    "                need += 2\n",
    "                if need % 2 == 1:\n",
    "                    # 插入一个右括号\n",
    "                    res += 1\n",
    "                    # 对右括号的需求减一\n",
    "                    need -= 1\n",
    "                    # 以上两句代码，是发生了需求转移。\n",
    "                    # 因为需求的右括号必须为偶数，所以need-1之后，但这个括号还是需要的，就把这个右括号加到了res头上。这时候就不区分左右括号了\n",
    "            elif c == \")\":\n",
    "                need -= 1\n",
    "                # 说明右括号太多了，多了一个\n",
    "                if need == -1:\n",
    "                    # 需要插入一个左括号\n",
    "                    res += 1\n",
    "                    # 同时，对右括号的需求变为 1\n",
    "                    need = 1\n",
    "        \n",
    "        return res + need\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # res, need = 0, 0\n",
    "        # for i in range(len(s)):\n",
    "        #     if s[i] == '(':\n",
    "        #         need += 2\n",
    "        #         # if need % 2 == 1:\n",
    "        #         #     res += 1\n",
    "        #         #     need -= 1\n",
    "        #     elif s[i] == ')':\n",
    "        #         need -= 1\n",
    "        #         if need == -1:\n",
    "        #             res += 1\n",
    "        #             need = 1\n",
    "        # return res + need"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        open_count = 0\n",
    "        insertions = 0\n",
    "        i = 0\n",
    "        \n",
    "        while i < n:\n",
    "            if s[i] == \"(\":\n",
    "                open_count += 1\n",
    "            elif s[i] == \")\":\n",
    "                if i + 1 < n and s[i + 1] == \")\":\n",
    "                    if open_count > 0:\n",
    "                        open_count -= 1\n",
    "                    else:\n",
    "                        insertions += 1\n",
    "                    i += 1\n",
    "                elif i + 1 == n:\n",
    "                    if open_count > 0:\n",
    "                        open_count -= 1\n",
    "                        insertions += 1\n",
    "                    else:\n",
    "                        insertions += 2\n",
    "                elif s[i + 1] == \"(\":\n",
    "                    if open_count > 0:\n",
    "                        open_count -= 1\n",
    "                        insertions += 1\n",
    "                    else:\n",
    "                        insertions += 2\n",
    "            i += 1\n",
    "        \n",
    "        return insertions + open_count * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        stack = 0\n",
    "        added = 0\n",
    "        for ch in s:\n",
    "            if ch == '(':\n",
    "                if stack % 2 != 0:\n",
    "                    added += 1\n",
    "                    stack -= 1\n",
    "                stack += 2\n",
    "            else:\n",
    "                if stack == 0:\n",
    "                    added += 1\n",
    "                    stack = 1\n",
    "                else:\n",
    "                    stack -= 1\n",
    "        added += stack\n",
    "        return added\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        s = s.replace('))', ']')\n",
    "        open_cnt = 0\n",
    "        ans = 0\n",
    "        for ii in s:\n",
    "            if ii == '(':\n",
    "                open_cnt += 1\n",
    "            elif ii == ']':\n",
    "                if open_cnt == 0:\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    open_cnt -= 1\n",
    "            elif ii == ')':\n",
    "                if open_cnt == 0:\n",
    "                    ans += 2\n",
    "                else:\n",
    "                    open_cnt -= 1\n",
    "                    ans += 1\n",
    "        \n",
    "        return open_cnt * 2 + ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s):\n",
    "        needed_right = 0  # 需要的右括号数量\n",
    "        insertions = 0  # 需要插入的括号数量\n",
    "\n",
    "        for char in s:\n",
    "            if char == '(':\n",
    "                needed_right += 2\n",
    "                # 如果需要的右括号数量是奇数，则插入一个右括号来平衡\n",
    "                if needed_right % 2 == 1:\n",
    "                    insertions += 1\n",
    "                    needed_right -= 1\n",
    "            else:  # char == ')'\n",
    "                needed_right -= 1\n",
    "                # 如果没有足够的左括号来匹配当前的右括号\n",
    "                if needed_right == -1:\n",
    "                    insertions += 1  # 插入一个左括号\n",
    "                    needed_right = 1  # 重置需要的右括号数量\n",
    "\n",
    "        # 最后，还需要考虑剩余未匹配的左括号\n",
    "        insertions += needed_right\n",
    "\n",
    "        return insertions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        res = 0\n",
    "        need = 0\n",
    "        for i in s:\n",
    "            if i == '(':\n",
    "                need += 2\n",
    "                if need % 2 == 1:\n",
    "                    res += 1\n",
    "                    need -= 1\n",
    "            else:\n",
    "                need -= 1\n",
    "                if need == -1:\n",
    "                    res += 1\n",
    "                    need = 1\n",
    "        return res + need"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://labuladong.github.io/algo/di-san-zha-24031/jing-dian--a94a0/ru-he-jie--306f6/\n",
    "# 这道题比较难，res不像前面的题（前面的题，res是维护插入左括号的数量），而这里不是\n",
    "# 这里的reshe need一起维护左右括号的平衡，不区分左右。其实本体一开始是区分左右的，一开始res维护左括号，need维护右括号，但是本题后来就不区分左右了\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        res, need = 0, 0\n",
    "        for c in s:\n",
    "            if c == \"(\":\n",
    "                need += 2\n",
    "                if need % 2 == 1:\n",
    "                    need -= 1\n",
    "                    res += 1\n",
    "            elif c == \")\":\n",
    "                need -= 1\n",
    "                if need == -1:\n",
    "                    res += 1\n",
    "                    need = 1\n",
    "        \n",
    "        return res + need\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # res, need = 0, 0\n",
    "        # for i in range(len(s)):\n",
    "        #     if s[i] == '(':\n",
    "        #         need += 2\n",
    "        #         # if need % 2 == 1:\n",
    "        #         #     res += 1\n",
    "        #         #     need -= 1\n",
    "        #     elif s[i] == ')':\n",
    "        #         need -= 1\n",
    "        #         if need == -1:\n",
    "        #             res += 1\n",
    "        #             need = 1\n",
    "        # return res + need"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        ans, cnt, stack = 0, 0, 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                if cnt == 0 or (cnt == 1 and stack == 0):\n",
    "                    stack += 1\n",
    "                ans += cnt\n",
    "                cnt = 0\n",
    "            else:\n",
    "                stack -= min(cnt, stack)\n",
    "                if cnt == 0 and stack == 0:\n",
    "                    ans += 1\n",
    "                cnt = cnt&1^1\n",
    "        return ans + cnt + 2 * (stack - min(cnt, stack))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        index = 0\n",
    "        length = len(s)\n",
    "        while index < length:\n",
    "            if s[index] == '(':\n",
    "                left += 1\n",
    "            else:\n",
    "                # 两个连续的')'\n",
    "                if index+1 < length and s[index+1] == ')':\n",
    "                    index += 1\n",
    "                else:\n",
    "                    #不是两个连续的')', 添加一个')'\n",
    "                    ans += 1\n",
    "                # 两个连续的')'抵消一个'('\n",
    "                if left > 0:\n",
    "                    left -= 1\n",
    "                else:\n",
    "                    # 增加一个'('\n",
    "                    ans += 1\n",
    "            index += 1\n",
    "        return ans + 2*left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        # 插入次数\n",
    "        res = 0\n",
    "        # 右括号需求\n",
    "        need = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '(':\n",
    "                need += 2\n",
    "                if need % 2 == 1:\n",
    "                    res += 1\n",
    "                    need -= 1\n",
    "            if s[i] == ')':\n",
    "                need -= 1\n",
    "                if need == -1:\n",
    "                    res += 1\n",
    "                    need = 1\n",
    "        return res + need"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        insertions, counter = 0, 0\n",
    "\n",
    "        for p in s:\n",
    "            if p == \"(\":\n",
    "                if counter % 2 != 0:\n",
    "                    insertions += 1\n",
    "                    counter -= 1\n",
    "                counter += 2\n",
    "            elif p == \")\":\n",
    "                counter -= 1\n",
    "                if counter < 0:\n",
    "                    insertions += 1\n",
    "                    counter += 2\n",
    "\n",
    "        if counter > 0:\n",
    "            insertions += counter\n",
    "        \n",
    "        return insertions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        res = 0\n",
    "        count = 0\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            print(\"i \", i)\n",
    "            if s[i] == \"(\":\n",
    "                count += 1\n",
    "            else:\n",
    "                if i+1 == len(s) or s[i+1] != \")\":\n",
    "                    res += 1\n",
    "                    i -= 1\n",
    "                i += 1\n",
    "                count -= 1\n",
    "            if count < 0:\n",
    "                res += 1\n",
    "                count = 0\n",
    "            i += 1\n",
    "            print(\"res \", res)\n",
    "        return res + count * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left_cnt = 0 \n",
    "        add = 0 \n",
    "        i = 0 \n",
    "        while i < n:\n",
    "            if s[i] == \"(\":\n",
    "                left_cnt += 1\n",
    "                i += 1\n",
    "            else:\n",
    "                if left_cnt > 0:\n",
    "                    left_cnt -= 1\n",
    "                else:\n",
    "                    add += 1\n",
    "                if i < n - 1 and s[i+1] == \")\":\n",
    "                    i += 2\n",
    "                else:\n",
    "                    add += 1\n",
    "                    i += 1\n",
    "        return left_cnt * 2 + add\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        need = 0\n",
    "        res = 0\n",
    "\n",
    "        for i in s: \n",
    "            if i == '(': \n",
    "\n",
    "                need += 2\n",
    "                if need %2 == 1: \n",
    "                    res += 1\n",
    "                    need -= 1\n",
    "            else: \n",
    "                need -= 1\n",
    "                if need == -1: \n",
    "                    res += 1\n",
    "                    need = 1\n",
    "        return need + res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        need = 0  # 需要的括号数\n",
    "        left = 0  # 没配对的左括号\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '(':\n",
    "                need += 2\n",
    "                if need % 2 == 1:\n",
    "                    need -= 1\n",
    "                    left += 1\n",
    "\n",
    "            if s[i] == ')':\n",
    "                need -= 1\n",
    "                if need == -1:\n",
    "                    left += 1\n",
    "                    need = 1\n",
    "\n",
    "        return left + need\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        res, need = 0, 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '(':\n",
    "                need += 2\n",
    "                if need % 2 == 1:\n",
    "                    res += 1\n",
    "                    need -= 1\n",
    "            elif s[i] == ')':\n",
    "                need -= 1\n",
    "                if need == -1:\n",
    "                    res += 1\n",
    "                    need = 1\n",
    "        return res + need\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        answer = 0 # 匹配过程中需要添加括号的次数\n",
    "        right_bracket_need = 0 # 左括号需要的右括号数量\n",
    "\n",
    "        for letter in s:\n",
    "            if letter == \"(\":\n",
    "                right_bracket_need += 2 \n",
    "                if right_bracket_need % 2:  #  需要的右括号数量为奇数\n",
    "                    right_bracket_need -= 1\n",
    "                    answer += 1 \n",
    "            else:\n",
    "                right_bracket_need -= 1 # 需要的右括号数量-1\n",
    "                if right_bracket_need == -1:\n",
    "                    answer += 1        # 添加一个左括号\n",
    "                    right_bracket_need = 1            \n",
    "        return answer + right_bracket_need\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        # 维护好balance，一个左括号增加2的balance，右括号必须连续\n",
    "        # 所以遇到单个右括号必须添加一个\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        balance = 0\n",
    "        i = 0\n",
    "        while i<n:\n",
    "            if s[i] == '(':\n",
    "                balance += 2\n",
    "            else:\n",
    "                if i<n-1 and s[i+1]==')':\n",
    "                    if balance>=2:\n",
    "                        balance -= 2\n",
    "                    else:\n",
    "                        res += 1\n",
    "                    i+=1\n",
    "                else:\n",
    "                    res += 1\n",
    "                    if balance>=2:\n",
    "                        balance -= 2\n",
    "                    else:\n",
    "                        res += 1\n",
    "                pass\n",
    "            i+=1\n",
    "        return res + balance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        cnt_l, i, n = 0, 0, len(s)\n",
    "        ans = 0\n",
    "        while i < n:    # 处理右括号，统计剩下的左括号\n",
    "            if s[i] == '(':\n",
    "                cnt_l += 1\n",
    "                i += 1\n",
    "            else:\n",
    "                if i + 1 < n and s[i + 1] == ')':   # 2个)括号\n",
    "                    if cnt_l > 0:\n",
    "                        cnt_l -= 1\n",
    "                    else:\n",
    "                        ans += 1\n",
    "                    i += 2\n",
    "                else:\n",
    "                    if cnt_l > 0:   # 1个)括号\n",
    "                        cnt_l -= 1\n",
    "                        ans += 1\n",
    "                    else:\n",
    "                        ans += 2\n",
    "                    i += 1\n",
    "        ans += cnt_l * 2        # 补充右括号\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minInsertions(self, s: str) -> int:\r\n",
    "        \"\"\"\r\n",
    "        这道题要求1个左括号需要和2个右括号匹配\r\n",
    "        \"\"\"\r\n",
    "        res, need = 0, 0  # res表示需要插入几个左括号, need表示当前需要多少个右括号\r\n",
    "        for c in s:\r\n",
    "            if c == '(':\r\n",
    "                if need % 2 == 1:  # 若右括号为奇数\r\n",
    "                    res += 1       # 则需要1个左括号\r\n",
    "                    need += 1\r\n",
    "                else:\r\n",
    "                    need += 2\r\n",
    "            elif c == ')':\r\n",
    "                need -= 1\r\n",
    "                if need == -1:  # 遇到多余的右括号\r\n",
    "                    res += 1  # 则需要1个左括号\r\n",
    "                    need = 1  # 现在又倒缺1个右括号\r\n",
    "        return res + need"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minInsertions(self, s: str) -> int:\r\n",
    "        \"\"\"\r\n",
    "        这道题要求1个左括号需要和2个右括号匹配\r\n",
    "        \"\"\"\r\n",
    "        res, need = 0, 0  # res表示需要插入几个左括号, need表示当前需要多少个右括号\r\n",
    "        for c in s:\r\n",
    "            if c == '(':\r\n",
    "                need += 2\r\n",
    "                if need % 2 == 1:\r\n",
    "                    res += 1\r\n",
    "                    need -= 1\r\n",
    "            elif c == ')':\r\n",
    "                need -= 1\r\n",
    "                if need == -1:\r\n",
    "                    res += 1\r\n",
    "                    need = 1\r\n",
    "        return res + need"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        stack = []\n",
    "        res = 0\n",
    "        s = collections.deque(s)\n",
    "        while s:\n",
    "            c = s.popleft()\n",
    "            if c == '(':\n",
    "                stack.append(c)\n",
    "            else:\n",
    "                if stack:\n",
    "                    if s and s[0] == ')':\n",
    "                        stack.pop()\n",
    "                        s.popleft()\n",
    "                    else:\n",
    "                        res += 1\n",
    "                        stack.pop()\n",
    "                else:\n",
    "                    if s and s[0] == ')':\n",
    "                        s.popleft()\n",
    "                        res += 1\n",
    "                    else:\n",
    "                        res += 2\n",
    "        \n",
    "        return res + len(stack) * 2\n",
    "                        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        result = 0\n",
    "        lst = []\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            if s[i] == \"(\":\n",
    "                lst.append(s[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                if i < len(s)-1 and s[i+1] == \")\":\n",
    "                    lst.append(\"))\")\n",
    "                    i += 2\n",
    "                else:\n",
    "                    result += 1\n",
    "                    lst.append(\"))\")\n",
    "                    i += 1\n",
    "        left = 0\n",
    "        for c in lst:\n",
    "            if c == \"(\":\n",
    "                left += 1\n",
    "            else:\n",
    "                if left:\n",
    "                    left -= 1\n",
    "                else:\n",
    "                    result += 1\n",
    "        result += 2 * left\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        left, right = 0, 0\n",
    "        if len(s) == 0: return 0\n",
    "\n",
    "        for p in s:\n",
    "            if p == \"(\":\n",
    "                right += 2\n",
    "                if right % 2 == 1:\n",
    "                    right -= 1\n",
    "                    left += 1\n",
    "            else:  # 右括号\n",
    "                right -= 1\n",
    "                if right == -1:\n",
    "                    right = 1\n",
    "                    left += 1\n",
    "            print(p, left, right)\n",
    "        return left + right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        stack = []\n",
    "        tmp = []\n",
    "        res = 0\n",
    "        for i in s:\n",
    "            if i == '(':\n",
    "                if len(stack) % 2 == 1:\n",
    "                    stack.pop()\n",
    "                    res += +1\n",
    "                if len(tmp)%2 == 1:\n",
    "                    res = res + (len(tmp)//2) + 2\n",
    "                else:\n",
    "                    res = res + (len(tmp)//2) \n",
    "                tmp = []\n",
    "\n",
    "            \n",
    "                stack.append('(')\n",
    "                stack.append('(')\n",
    "                #print(stack)\n",
    "            else:\n",
    "                if stack:\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    tmp.append(')')\n",
    "                #print(stack,tmp)\n",
    "            #print(stack,tmp,res)\n",
    "\n",
    "        if len(tmp)%2 == 1:\n",
    "            return res + len(stack) + (len(tmp)//2) + 2\n",
    "        else:\n",
    "            return res + len(stack) + (len(tmp)//2) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "\n",
    "        stack = []\n",
    "        rlt = 0\n",
    "        cur = 0\n",
    "        for ch in s:\n",
    "            if ch == '(':\n",
    "                if cur > 0:\n",
    "                    if cur % 2 == 1:\n",
    "                        cur += 1\n",
    "                        rlt += 1\n",
    "                        stack.append(')')\n",
    "                stack.append(ch)\n",
    "                cur = 0\n",
    "            else:\n",
    "                stack.append(ch)\n",
    "                cur += 1\n",
    "        s = \"\".join(stack)\n",
    "        stack = []\n",
    "        for ch in s:\n",
    "            if ch == '(':\n",
    "                stack.append(ch)\n",
    "            else:\n",
    "                if len(stack) == 0:\n",
    "                    rlt += 1\n",
    "                    stack.append('(')\n",
    "                stack.append(ch)\n",
    "\n",
    "                if len(stack) >= 3 and stack[-3] == '(' and stack[-2] == ')' and stack[-1] == ')':\n",
    "                    stack.pop()\n",
    "                    stack.pop()\n",
    "                    stack.pop()\n",
    "        while len(stack) != 0:\n",
    "            rlt += 1\n",
    "            stack.append(')')\n",
    "            if len(stack) >= 3 and stack[-3] == '(' and stack[-2] == ')' and stack[-1] == ')':\n",
    "                    stack.pop()\n",
    "                    stack.pop()\n",
    "                    stack.pop()\n",
    "        return rlt\n",
    "\n",
    "    \n",
    "      \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        stack=[]\n",
    "        count=0\n",
    "        ans=0\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            if s[i]==')':\n",
    "                count+=1\n",
    "                stack.append(')')\n",
    "            if s[i]=='(':\n",
    "                if count%2==0:\n",
    "                    stack.append('(')\n",
    "                else:\n",
    "                    stack.append(')')\n",
    "                    stack.append('(')\n",
    "                    count+=1\n",
    "        ans+=len(stack)-len(s)\n",
    "        s=''.join(stack[::-1])\n",
    "        \n",
    "\n",
    "\n",
    "        left=0\n",
    "        right=0\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            if s[i]==')':\n",
    "                right+=1\n",
    "            if s[i]=='(':\n",
    "                left+=1\n",
    "            if left*2>right:\n",
    "                ans+=left*2-right\n",
    "                right=left*2\n",
    "\n",
    "        \n",
    "        if right%2:\n",
    "            right+=1\n",
    "            ans+=1\n",
    "        ans+=right//2-left\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        stack = []\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if s[i] == '(':\n",
    "                stack.append('(')\n",
    "                i += 1\n",
    "            else: # s[i] == ')'\n",
    "                if not stack:\n",
    "                    ans += 1\n",
    "                    i += 1\n",
    "                    if i == n :\n",
    "                        ans += 1\n",
    "                        break\n",
    "                    elif i < n and s[i] == ')':\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        ans += 1\n",
    "\n",
    "                else:\n",
    "                    stack.pop(-1)\n",
    "                    i += 1\n",
    "                    if i == n:\n",
    "                        ans += 1\n",
    "                        break\n",
    "                    elif i < n and s[i] == ')':\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        ans += 1\n",
    "        print(stack)\n",
    "        ans += (2 * len(stack))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        stack = []\n",
    "        op = 0\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            c = s[i]\n",
    "            if c == '(':\n",
    "                stack.append(c)\n",
    "                i += 1\n",
    "            else:\n",
    "                if i == len(s) -1 or s[i + 1] != ')':\n",
    "                    op += 1\n",
    "                    i -= 1\n",
    "                if len(stack) == 0:\n",
    "                    op += 1\n",
    "                else:\n",
    "                    stack = stack[:-1]\n",
    "                i += 2\n",
    "\n",
    "        return op + 2*len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "\n",
    "        queue = deque(s)\n",
    "        needs = 0\n",
    "        res = 0\n",
    "        while queue:\n",
    "            c = queue.popleft()\n",
    "            if c == \"(\":\n",
    "                needs += 2 #一个左括号需要两个右括号\n",
    "                if needs % 2 == 1:#如果是奇数，需增加多一个右括号\n",
    "                    res += 1 #插入一个右括号\n",
    "                    needs -= 1 #对右括号的需求减一\n",
    "            elif c == \")\":\n",
    "                needs -= 1\n",
    "                if needs == -1: #说明右括号太多了\n",
    "                    res += 1 #需要插入一个左括号\n",
    "                    needs = 1 #同时，对右括号的需求变为 1\n",
    "\n",
    "        return res + needs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        listS1 = []\n",
    "        listS2 = []\n",
    "        stack = []\n",
    "        R = 0\n",
    "        c = 0\n",
    "        n = 0\n",
    "        i = 0\n",
    "        for t in s:\n",
    "            if t == \"(\":\n",
    "                if c % 2 == 1:\n",
    "                    listS1.append(\")\")\n",
    "                    n = n + 1\n",
    "                    R = R + 1\n",
    "                listS1.append(t)\n",
    "                n = n + 1\n",
    "                c = 0\n",
    "            else:\n",
    "                listS1.append(t)\n",
    "                n = n + 1\n",
    "                c = c + 1\n",
    "        if c % 2 == 1:\n",
    "            listS1.append(\")\")\n",
    "            n = n + 1\n",
    "            R = R + 1\n",
    "        while i < n:\n",
    "            if listS1[i] == \"(\":\n",
    "                listS2.append(listS1[i])\n",
    "                i = i + 1\n",
    "            else:\n",
    "                listS2.append(listS1[i])\n",
    "                i = i + 2\n",
    "        print(\"listS2 = \",listS2)\n",
    "        for t in listS2:\n",
    "            if t == \"(\":\n",
    "                stack.append(t)\n",
    "            else:\n",
    "                if stack and stack[-1] == \"(\":\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    stack.append(\")\")\n",
    "        print(\"R = \", R)\n",
    "        print(\"stack = \", stack)\n",
    "        for t in stack:\n",
    "            if t == \"(\":\n",
    "                R = R + 2\n",
    "            else:\n",
    "                R = R + 1\n",
    "        return R\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        res = 0\n",
    "        arr = []\n",
    "        cnt = 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                if cnt % 2 == 1:\n",
    "                    arr.append(')')\n",
    "                    res += 1\n",
    "                cnt = 0\n",
    "                arr.append(c)\n",
    "            else:\n",
    "                cnt += 1\n",
    "                arr.append(c)\n",
    "        if cnt % 2 == 1:\n",
    "            arr.append(')')\n",
    "            res += 1\n",
    "        arr.reverse()\n",
    "        stack = []\n",
    "        for c in arr:\n",
    "            if c == ')':\n",
    "                stack.append(c)\n",
    "            else:\n",
    "                if len(stack) >= 2:\n",
    "                    stack.pop()\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    res += 2\n",
    "        while stack:\n",
    "            stack.pop()\n",
    "            stack.pop()\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "\n",
    "        d = deque()\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        rs = 0\n",
    "        index = 0\n",
    "        while True:\n",
    "            if index == n:\n",
    "                break\n",
    "            c = s[index]\n",
    "            if c == '(':\n",
    "                # 遇到 ( 入栈\n",
    "                d.append(c)\n",
    "            else:\n",
    "                # 遇到 ) 出栈\n",
    "                # 下一个字符也应该是 ), 否则应该插入\n",
    "                if index + 1 < n and s[index + 1] == ')':\n",
    "                    index += 1\n",
    "                else:\n",
    "                     rs += 1\n",
    "                # 栈中有 ( 则出栈, 否则缺少 ( 应该插入\n",
    "                if d:     \n",
    "                    d.pop()\n",
    "                else:\n",
    "                    rs += 1\n",
    "\n",
    "            index += 1\n",
    "        \n",
    "        # 栈中多余的 ( 应该多插入 ))\n",
    "        rs += len(d) * 2\n",
    "\n",
    "        return rs\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "\n",
    "        d = deque()\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        rs = 0\n",
    "        index = 0\n",
    "        while True:\n",
    "            if index == n:\n",
    "                break\n",
    "            c = s[index]\n",
    "            if c == '(':\n",
    "                # 遇到 ( 入栈\n",
    "                d.append(c)\n",
    "            else:\n",
    "                # 遇到 ) 出栈\n",
    "                # 下一个字符也应该是 ), 否则应该插入\n",
    "                if index + 1 < n and s[index + 1] == ')':\n",
    "                    index += 1\n",
    "                else:\n",
    "                     rs += 1\n",
    "                # 栈中有 ( 则出栈, 否则缺少 ( 应该插入\n",
    "                if d:     \n",
    "                    d.pop()\n",
    "                else:\n",
    "                    rs += 1\n",
    "\n",
    "            index += 1\n",
    "        \n",
    "        # 栈中多余的 ( 应该多插入 ))\n",
    "        rs += len(d) * 2\n",
    "\n",
    "        return rs\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        \n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "        tmp = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == '(':\n",
    "                if tmp % 2 == 1:\n",
    "                    s = s[:i + 1] + ')' + s[i + 1:]\n",
    "                    ans += 1\n",
    "                    tmp = 0\n",
    "            else:\n",
    "                tmp += 1\n",
    "        \n",
    "        if tmp%2==1:\n",
    "            s=')'+s\n",
    "            ans+=1\n",
    "\n",
    "        stack=[]\n",
    "        \n",
    "        for c in s:\n",
    "            if c=='(':\n",
    "                stack.append('(')\n",
    "                stack.append('(')\n",
    "                \n",
    "            else:\n",
    "                if stack and stack[-1]=='(':\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    stack.append(')')\n",
    "        \n",
    "        r=0\n",
    "        \n",
    "        for i in stack:\n",
    "            if i==')':\n",
    "                r+=1\n",
    "            else:\n",
    "                break\n",
    "        ans+=len(stack)-r\n",
    "        ans+=r//2 if r%2==0 else (r+1)//2+1\n",
    "        return ans\n",
    "            \n",
    "                \n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        cnt=0\n",
    "        i=0\n",
    "        n=len(s)\n",
    "        stack=[]\n",
    "        while i<n:\n",
    "            if s[i]==\"(\":\n",
    "                stack.append(s[i])\n",
    "            elif s[i]==\")\":\n",
    "                if i+1<n and s[i+1]==\")\":\n",
    "                    i=i+1\n",
    "                else:\n",
    "                    cnt+=1\n",
    "                if len(stack):\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    cnt+=1\n",
    "            i=i+1\n",
    "        if len(stack):\n",
    "            cnt+=len(stack)*2\n",
    "        return cnt\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 两种套路：1. 贪心greedy；2. 栈stack -> 栈方法内存超限\n",
    "# 贪心：count计数未匹配到的左括号，count<0说明有未匹配的右括号\n",
    "# 遇到左括号：count += 1\n",
    "# 遇到连续两个右括号：count -= 1\n",
    "# 只遇到一个右括号：只有一个右括号无法跟其他括号匹配，必须加上一个右括号，再匹配一个左括号（也就是count -= 1）\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        stack = []\n",
    "        # p = 0\n",
    "        res = 0\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            c = s[i]\n",
    "            if c == \"(\":\n",
    "                stack.append(c)\n",
    "            elif c == \")\":\n",
    "                i += 1\n",
    "                if i >= n:\n",
    "                    if stack:\n",
    "                        stack.pop()\n",
    "                        res += 1\n",
    "                    else:\n",
    "                        res += 2\n",
    "                    # res += 1\n",
    "                    # if stack: stack.pop()\n",
    "                    # else: res += 2\n",
    "                    continue\n",
    "                c2 = s[i]\n",
    "                if stack and c2 == \")\":\n",
    "                    stack.pop()\n",
    "                elif stack and c2 == \"(\":\n",
    "                    stack.pop()\n",
    "                    stack.append(c2)\n",
    "                    res += 1\n",
    "                elif not stack and c2 == \")\":\n",
    "                    res += 1\n",
    "                elif not stack and c2 == \"(\":\n",
    "                    res += 2\n",
    "                    stack.append(c2)\n",
    "            i += 1\n",
    "        if stack:\n",
    "            return 2 * len(stack) + res\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "        # while p < n:\n",
    "        #     if s[p] == \"(\":\n",
    "        #         stack.append(\"(\")\n",
    "        #     if s[p] == \")\":\n",
    "        #         p += 1\n",
    "        #         if s[p] == \")\":\n",
    "        #             if stack and stack[-1] == \"(\":\n",
    "        #                 stack.pop()\n",
    "        #             else:\n",
    "        #                 res += 1\n",
    "        #         else:\n",
    "        #             res += 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        stack = []\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        cnt = 0\n",
    "        while i < n:\n",
    "            # print('s[i] = ',s[i])\n",
    "            if s[i] == \"(\":\n",
    "                stack.append(\"(\")\n",
    "            elif s[i] == \")\":\n",
    "                if i+1 < n and s[i+1] == \")\":\n",
    "                    i += 1\n",
    "                    if len(stack):\n",
    "                        stack.pop()\n",
    "                    else:\n",
    "                        cnt += 1\n",
    "                else:\n",
    "                    if len(stack):\n",
    "                        stack.pop()\n",
    "                        cnt += 1\n",
    "                    else:\n",
    "                        cnt += 2\n",
    "            i += 1\n",
    "        # print(stack,cnt)\n",
    "        return 2*len(stack) + cnt\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        stack = []\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        cnt = 0\n",
    "        while i < n:\n",
    "            # print('s[i] = ',s[i])\n",
    "            if s[i] == \"(\":\n",
    "                stack.append(\"(\")\n",
    "            elif s[i] == \")\":\n",
    "                if i+1 < n and s[i+1] == \")\":\n",
    "                    i += 1\n",
    "                    if len(stack):\n",
    "                        stack.pop()\n",
    "                    else:\n",
    "                        cnt += 1\n",
    "                else:\n",
    "                    if len(stack):\n",
    "                        stack.pop()\n",
    "                        cnt += 1\n",
    "                    else:\n",
    "                        cnt += 2\n",
    "            i += 1\n",
    "        # print(stack,cnt)\n",
    "        return 2*len(stack) + cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 两种套路：1. 贪心greedy；2. 栈stack -> 栈方法内存超限\n",
    "# 贪心：count计数未匹配到的左括号，count<0说明有未匹配的右括号\n",
    "# 遇到左括号：count += 1\n",
    "# 遇到连续两个右括号：count -= 1\n",
    "# 只遇到一个右括号：只有一个右括号无法跟其他括号匹配，必须加上一个右括号，再匹配一个左括号（也就是count -= 1）\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        stack = []\n",
    "        # p = 0\n",
    "        res = 0\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            c = s[i]\n",
    "            if c == \"(\":\n",
    "                stack.append(c)\n",
    "            elif c == \")\":\n",
    "                i += 1\n",
    "                if i >= n:\n",
    "                    if stack:\n",
    "                        stack.pop()\n",
    "                        res += 1\n",
    "                    else:\n",
    "                        res += 2\n",
    "                    # res += 1\n",
    "                    # if stack: stack.pop()\n",
    "                    # else: res += 2\n",
    "                    continue\n",
    "                c2 = s[i]\n",
    "                if stack and c2 == \")\":\n",
    "                    stack.pop()\n",
    "                elif stack and c2 == \"(\":\n",
    "                    # stack.pop()\n",
    "                    # stack.append(c2) # 这两句相当于栈中元素没变，可以省略\n",
    "                    res += 1\n",
    "                elif not stack and c2 == \")\":\n",
    "                    res += 1   # 两个res可以进一步整合\n",
    "                elif not stack and c2 == \"(\":\n",
    "                    res += 2\n",
    "                    stack.append(c2)\n",
    "                # else:\n",
    "                #     res += 1\n",
    "            i += 1\n",
    "        if stack:\n",
    "            return 2 * len(stack) + res\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "        # while p < n:\n",
    "        #     if s[p] == \"(\":\n",
    "        #         stack.append(\"(\")\n",
    "        #     if s[p] == \")\":\n",
    "        #         p += 1\n",
    "        #         if s[p] == \")\":\n",
    "        #             if stack and stack[-1] == \"(\":\n",
    "        #                 stack.pop()\n",
    "        #             else:\n",
    "        #                 res += 1\n",
    "        #         else:\n",
    "        #             res += 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        st = []\n",
    "        ans = 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                if not st or st[-1] == '(':\n",
    "                    st.append(c)\n",
    "                else:\n",
    "                    ans += 1\n",
    "                    st.pop()\n",
    "                    st.pop()\n",
    "                    st.append(c)\n",
    "            else:\n",
    "                if not st:\n",
    "                    st.append('(')\n",
    "                    st.append(c)\n",
    "                    ans += 1\n",
    "                elif st[-1] == '(':\n",
    "                    st.append(c)\n",
    "                else:\n",
    "                    st.pop()\n",
    "                    st.pop()\n",
    "        while st:\n",
    "            if st.pop() == '(':\n",
    "                ans += 2\n",
    "            else:\n",
    "                st.pop()\n",
    "                ans += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, words: str) -> int:\n",
    "\n",
    "        q=[]\n",
    "        # print(\"(())())))\".replace(\"))\",\"2\"))\n",
    "        words=words.replace(\"))\",\"2\")\n",
    "        print(words)\n",
    "        ans=0\n",
    "        for w in words:\n",
    "            if w==\"(\":\n",
    "                q.append(w)\n",
    "            elif w==\")\":\n",
    "                if len(q)==0:\n",
    "                    ans+=2\n",
    "                elif q[-1]==\"(\":\n",
    "                    ans+=1\n",
    "                    q.pop()\n",
    "            elif w==\"2\":\n",
    "                if len(q)==0:\n",
    "                    ans+=1\n",
    "                elif q[-1]==\"(\":\n",
    "                    ans+=0\n",
    "                    q.pop()\n",
    "        \n",
    "        return ans+2*len(q)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s:str)->int:\n",
    "        stack = []\n",
    "        res = 0\n",
    "        i = 0\n",
    "        n = len(s)\n",
    "        while i<n:\n",
    "            if s[i] == '(':\n",
    "                stack.append(s[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                if i+1 < n and s[i+1] ==')':\n",
    "                    if stack:\n",
    "                        stack.pop()\n",
    "                    else:\n",
    "                        res += 1\n",
    "                    i += 2\n",
    "                else:\n",
    "                    if stack:\n",
    "                        stack.pop()\n",
    "                        res += 1\n",
    "                    else:\n",
    "                        res += 2\n",
    "                    i += 1\n",
    "        res += len(stack)*2\n",
    "        return res                                     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        idx = 0\n",
    "        ans = 0\n",
    "        temp = []\n",
    "\n",
    "        while idx < len(s):\n",
    "            if s[idx] == '(':\n",
    "                temp.append('(')\n",
    "                idx += 1\n",
    "            elif idx == len(s) - 1:\n",
    "                if temp:\n",
    "                    temp.pop()\n",
    "                    ans += 1\n",
    "                    idx += 1\n",
    "                else:\n",
    "                    ans += 2\n",
    "                    idx += 1\n",
    "            else:\n",
    "                if temp and s[idx + 1] == ')':\n",
    "                    temp.pop()\n",
    "                    idx += 2\n",
    "                elif temp and s[idx + 1] != ')':\n",
    "                    temp.pop()\n",
    "                    ans += 1\n",
    "                    idx += 1\n",
    "                elif not temp and s[idx + 1] == ')':\n",
    "                    ans += 1\n",
    "                    idx += 2\n",
    "                else:\n",
    "                    ans += 2\n",
    "                    idx += 1\n",
    "        return ans + 2 * len(temp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 两种套路：1. 贪心greedy；2. 栈stack -> 栈方法内存超限\n",
    "# 贪心：count计数未匹配到的左括号，count<0说明有未匹配的右括号\n",
    "# 遇到左括号：count += 1\n",
    "# 遇到连续两个右括号：count -= 1\n",
    "# 只遇到一个右括号：只有一个右括号无法跟其他括号匹配，必须加上一个右括号，再匹配一个左括号（也就是count -= 1）\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        stack = []\n",
    "        # p = 0\n",
    "        res = 0\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            c = s[i]\n",
    "            if c == \"(\":\n",
    "                stack.append(c)\n",
    "            elif c == \")\":\n",
    "                i += 1\n",
    "                if i >= n:\n",
    "                    if stack:\n",
    "                        stack.pop()\n",
    "                        res += 1\n",
    "                    else:\n",
    "                        res += 2\n",
    "                    # res += 1\n",
    "                    # if stack: stack.pop()\n",
    "                    # else: res += 2\n",
    "                    continue\n",
    "                c2 = s[i]\n",
    "                if stack and c2 == \")\":\n",
    "                    stack.pop()\n",
    "                elif stack and c2 == \"(\":\n",
    "                    # stack.pop()\n",
    "                    # stack.append(c2) # 这两句相当于栈中元素没变，可以省略\n",
    "                    res += 1\n",
    "                elif not stack and c2 == \")\":\n",
    "                    res += 1\n",
    "                elif not stack and c2 == \"(\":\n",
    "                    res += 2\n",
    "                    stack.append(c2)\n",
    "            i += 1\n",
    "        if stack:\n",
    "            return 2 * len(stack) + res\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "        # while p < n:\n",
    "        #     if s[p] == \"(\":\n",
    "        #         stack.append(\"(\")\n",
    "        #     if s[p] == \")\":\n",
    "        #         p += 1\n",
    "        #         if s[p] == \")\":\n",
    "        #             if stack and stack[-1] == \"(\":\n",
    "        #                 stack.pop()\n",
    "        #             else:\n",
    "        #                 res += 1\n",
    "        #         else:\n",
    "        #             res += 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        if not s:\n",
    "            return None \n",
    "\n",
    "        stack = []\n",
    "        counter = 0\n",
    "        res = 0\n",
    "        while counter < len(s):\n",
    "            if s[counter] == '(':\n",
    "                stack.append(s[counter])\n",
    "                counter += 1\n",
    "            else:\n",
    "                # s[counter] == ')'\n",
    "                if counter < len(s) - 1 and s[counter + 1] == ')': # not the last one \n",
    "                    if stack:\n",
    "                        stack.pop()\n",
    "                    else: \n",
    "                        res += 1\n",
    "                    counter += 2\n",
    "                \n",
    "                else:\n",
    "                    counter += 1\n",
    "                    if stack:\n",
    "                        stack.pop()\n",
    "                        res += 1\n",
    "                    else:\n",
    "                        res += 2\n",
    "        \n",
    "        return res + 2* len(stack)\n",
    "                \n",
    "                \n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return res + len(stk) * 2 if stk else res         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        res = 0\n",
    "        i = 0\n",
    "        while i < len(s) and s[i] == ')':\n",
    "            i += 1\n",
    "        \n",
    "        size = i\n",
    "        if size % 2 == 0:\n",
    "            res += size // 2\n",
    "        else:\n",
    "            res += size // 2 + 2\n",
    "\n",
    "        if i == len(s):\n",
    "            return res\n",
    "        \n",
    "        stack = []\n",
    "        while i < len(s):\n",
    "            if s[i] == '(':\n",
    "                stack.append('(')\n",
    "                i += 1\n",
    "            else:\n",
    "                if i + 1 == len(s) or s[i + 1] == '(':\n",
    "                    res += 1 # 借一个\n",
    "                    if stack and stack[-1] == '(':\n",
    "                        stack.pop()\n",
    "                    else:\n",
    "                        res += 1\n",
    "                    i += 1\n",
    "                else: # s[i + 1] == ')'\n",
    "                    if stack and stack[-1] == '(':\n",
    "                        stack.pop()\n",
    "                    else:\n",
    "                        res += 1\n",
    "                    \n",
    "                    i += 2\n",
    "\n",
    "        return res + len(stack) * 2\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        stack = []\n",
    "        i = res = 0\n",
    "        while i < len(s):\n",
    "            item = s[i]\n",
    "            if item == '(':\n",
    "                stack.append(item)\n",
    "            else:\n",
    "                if len(stack):\n",
    "                    if i + 1 < len(s) and s[i + 1] == ')':\n",
    "                        stack.pop()\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        stack.pop()\n",
    "                        res += 1\n",
    "                else:\n",
    "                    if i + 1 < len(s) and s[i + 1] == ')':\n",
    "                        res += 1\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        res += 2\n",
    "            i += 1\n",
    "\n",
    "        return res + len(stack) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        s_stack, cnt, i= [], 0, 0\n",
    "        while i < len(s):\n",
    "            c = s[i]\n",
    "            if c in \"(\":\n",
    "                s_stack.append(c)\n",
    "            else:\n",
    "                if c in \")\":\n",
    "                    if not s_stack:\n",
    "                        cnt +=1\n",
    "                        if i== len(s)-1 or (i<len(s)-1 and s[i+1] not in \")\"):\n",
    "                            cnt +=1\n",
    "                        else:\n",
    "                            i+=1\n",
    "                    else:\n",
    "                        s_stack.pop()\n",
    "                        if i== len(s)-1 or (i<len(s)-1 and s[i+1] not in \")\"):\n",
    "                            cnt +=1\n",
    "                        else:\n",
    "                            i +=1\n",
    "            i+=1\n",
    "        return cnt + len(s_stack)*2\n",
    "                        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        stack1 = []\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if s[i] == \"(\":\n",
    "                stack1.append(\"(\")\n",
    "            elif s[i] == \")\":\n",
    "                if i + 1 < n and s[i + 1] == \")\":\n",
    "                    if stack1:\n",
    "                        stack1.pop()\n",
    "                    else:\n",
    "                        ans += 1\n",
    "                    i += 1\n",
    "                elif i + 1 == n:\n",
    "                    if stack1:\n",
    "                        stack1.pop()\n",
    "                        ans += 1\n",
    "                    else:\n",
    "                        ans += 2\n",
    "                elif s[i + 1] == \"(\":\n",
    "                    if stack1:\n",
    "                        stack1.pop()\n",
    "                        ans += 1\n",
    "                    else:\n",
    "                        ans += 2\n",
    "            i += 1\n",
    "        return ans + len(stack1) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        stack = []\n",
    "        need = 0\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if s[i] == '(':\n",
    "                stack.append(s[i])\n",
    "                need += 2\n",
    "            else:\n",
    "                if not stack:\n",
    "                    need += 1\n",
    "                    if i + 1 < n and s[i + 1] == ')':\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        need += 1\n",
    "                else:\n",
    "                    stack.pop()\n",
    "                    if i + 1 < n and s[i + 1] == ')':\n",
    "                        i += 1\n",
    "                        need -= 2\n",
    "                    else:\n",
    "                        need -= 1\n",
    "           \n",
    "            i += 1\n",
    "        \n",
    "        return need\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        res = 0\n",
    "        n = len(s)\n",
    "        stack = []\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if s[i] == '(':\n",
    "                stack.append(s[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                if i + 1 < n and s[i + 1] == ')':\n",
    "                    if len(stack) > 0:\n",
    "                        stack.pop()\n",
    "                    else:\n",
    "                        res += 1\n",
    "                    i += 2\n",
    "                else:\n",
    "                    if len(stack) > 0:\n",
    "                        stack.pop()\n",
    "                        res += 1\n",
    "                    else:\n",
    "                        res += 2\n",
    "                    i += 1\n",
    "        res += 2 * len(stack)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        s=s.replace(\"))\",\"]\")# 将所有连续后括号换成]\n",
    "        stack = []\n",
    "        ans = 0\n",
    "        for st in s:\n",
    "            if st==\"(\":\n",
    "                stack.append(\"(\")#如果是前括号加入栈\n",
    "            elif st==\"]\":\n",
    "                # 两个连续后括号如果栈为空，则插入(，如果非空弹出最后一个\n",
    "                if not stack: ans+=1\n",
    "                else: stack.pop()\n",
    "            else:\n",
    "                # 单个后括号，如果空,在该括号之前插入\"(\" 且还需补上”）“        \n",
    "                if not stack: ans+=2\n",
    "                else:\n",
    "                # 如果非空补上一个后括号\n",
    "                    stack.pop()\n",
    "                    ans+=1\n",
    "        return ans+len(stack)*2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        s=s.replace(\"))\",\"]\")# 将所有连续后括号换成]\n",
    "        stack = []\n",
    "        ans = 0\n",
    "        for st in s:\n",
    "            if st==\"(\":\n",
    "                stack.append(\"(\")#如果是前括号加入栈\n",
    "            elif st==\"]\":\n",
    "                # 两个连续后括号如果栈为空，则插入(，如果非空弹出最后一个\n",
    "                if not stack: ans+=1\n",
    "                else: stack.pop()\n",
    "            else:\n",
    "                # 单个后括号，如果空,在该括号之前插入\"(\" 且还需补上”）“        \n",
    "                if not stack: ans+=2\n",
    "                else:\n",
    "                # 如果非空补上一个后括号\n",
    "                    stack.pop()\n",
    "                    ans+=1\n",
    "        return ans+len(stack)*2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        st = []\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                if not st or st[-1] == '(':\n",
    "                    st.append(c)\n",
    "                elif st[-1] == ')':\n",
    "                    st.pop()\n",
    "                    st.pop()\n",
    "                    st.append(c)\n",
    "                    ans += 1\n",
    "            else:\n",
    "                if not st:\n",
    "                    st.append('(')\n",
    "                    ans += 1\n",
    "                    st.append(c)\n",
    "                elif st[-1] == '(':\n",
    "                    st.append(c)\n",
    "                elif st[-1] == ')':\n",
    "                    st.pop()\n",
    "                    st.pop()\n",
    "        ans += st.count('(') * 2 - st.count(')')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        ans, stack = 0, []\n",
    "        i, n = 0, len(s)\n",
    "        while i < n:\n",
    "            if s[i] == \"(\":\n",
    "                stack.append(s[i])\n",
    "            else:\n",
    "                i += 1\n",
    "                if i < n:\n",
    "                    if s[i] == \")\":\n",
    "                        if stack:\n",
    "                            stack.pop()\n",
    "                        else:\n",
    "                            ans += 1\n",
    "                    else:\n",
    "                        if stack:\n",
    "                            stack.pop()\n",
    "                            ans += 1\n",
    "                        else:\n",
    "                            ans += 2\n",
    "                        stack.append(s[i])\n",
    "                else:\n",
    "                    if stack:\n",
    "                        stack.pop()\n",
    "                        ans += 1\n",
    "                    else:\n",
    "                        ans += 2\n",
    "            i += 1\n",
    "        ans += 2 * len(stack)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        s=s.replace(\"))\",\"]\")# 将所有连续后括号换成]\n",
    "        stack = []\n",
    "        ans = 0\n",
    "        for st in s:\n",
    "            if st==\"(\":\n",
    "                stack.append(\"(\")#如果是前括号加入栈\n",
    "            elif st==\"]\":\n",
    "                # 两个连续后括号如果栈为空，则插入(，如果非空弹出最后一个\n",
    "                if not stack: ans+=1\n",
    "                else: stack.pop()\n",
    "            else:\n",
    "                # 单个后括号，如果空,在该括号之前插入\"(\" 且还需补上”）“        \n",
    "                if not stack: ans+=2\n",
    "                else:\n",
    "                # 如果非空补上一个后括号\n",
    "                    stack.pop()\n",
    "                    ans+=1\n",
    "        return ans+len(stack)*2\n",
    "\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
